#include "Linklist.h"


//创建一个链表
PNode creat_linklist()
{
    Datatype num;//num用来保存用户输入的数据
    //创建一个节点
    PNode pnew = NULL;//用来保存新节点的地址
    PNode first = NULL;//用来保存链表首节点地址
    PNode last = NULL;//用来保存链表尾节点地址
    while(1)
    {
        //获取数据，创建节点
        scanf("%d",&num);
        if(num == 0)
            break;
        //修改空间大小，并且赋值
        pnew = (PNode)malloc(sizeof(*pnew));
        pnew->data = num;
        pnew->next = NULL;
        //将新节点加入到链表中
        if(first == NULL)//从无到有
        {
            first = pnew;
            last = pnew;
        }
        else//从少到多
        {
            //尾插法
			last->next = pnew;
			last = pnew;
			//头插法
			//pnew->next = first;
			//first = pnew;
        }
    }
    return first;
}

//创建一个升序链表
PNode creat_high_linklistlist()
{
    Datatype num;//d用来保存用户输入的数据
	struct node *pnew=NULL;//用来保存新结点的地址
	struct node *first=NULL;//用来保存链表首结点的地址
	struct node *last=NULL;//用来保存链表尾结点的地址 
	while(1)
	{
		//step:每获得一个数据，就去创建一个节点
		scanf("%d",&num);
		if(num == 0)//规定每次输入的数据一0结束
		{
			break;
		}
		pnew=(PNode)malloc(sizeof(*pnew));
		//step2:获得的数据赋值给结点的数据域
		pnew->data = num;
		pnew->next = NULL;
		//step3:把给新结点加入到链表中
		//真么判断时从无到有
		if(first == NULL)
		{
			first = pnew;
			last = pnew;
		}
		else//从少到多
		{	//可能有三种可能
			if(pnew->data <= first->data)//pnew最小
			{
				pnew->next = first;
				first = pnew;
			}
			else if(pnew->data >= last->data)//pnew最大
			{
				last->next = pnew;
				last = pnew;
			}
			else//两者之间
			{
				//先查找到要插入的位置，需要两个遍历指针，一前一后逐步推进
				PNode p = first;
				PNode pre = p;
				while(1)//安步推进
				{
					if(p->data > pnew->data)//找到
					{
						break;
					}
					pre = p;//类似于i++
					p = p->next;
				}
				pre->next = pnew;//pre < pnew < p
				pnew->next = p;  //放置位置
			}
		}
	}
	return first;//返回首地址
}



/*
2.删除指定的链表中的值X(假设X唯一)
    (直接做扩展)扩展:删除链表中所有的X
    Node *deleteX(Elemtype x ,Node *list)
*/
PNode delete_x_linklist(Datatype x,PNode list)
{
    PNode pre = NULL;
    PNode p = NULL;
    
    p = list;
    while(p)
    {
        if(p->data == x)//是x时
        {
            if(p == list)//第一个就是x
            {
                //更新首节点
                list = list->next;
                p->next = NULL;
                free(p);
                p = list;
            }
            else
            {
                pre->next = p->next;
                p->next = NULL;
                free(p);
                p = pre->next;
            }
        }
        else//不是x时
        {
            pre = p;//正常循环
            p = p->next;
        }
    }
    return list;
}

/*
3.写一个函数,反序输出单链表中各个节点的值(不能改变原链表中的内容和结构)
    void printReverList(Node *list)
    单纯反序打印,思路：遍历一次链表，取出原链表中数据，使用头插法建立一个新链表
*/  
PNode printf_rever_linklist(PNode list)
{

	PNode p = list;
	PNode first = NULL;
	PNode pnew = NULL;
	while(p != NULL)
	{
		if(pnew == 0)
		{
			break;
		}
		pnew = (PNode)malloc(sizeof(Node));
		pnew->data = p->data;
		pnew->next = NULL;
		//头插法
		pnew->next = first;
		first = pnew;
		p = p->next;		
	}
	return first;

	/* //递归算法
		if(list == NULL)
		{
			return;
		}
		printf_rever_linklist(list->next);
		printf("%d",list->data);
	*/


/*
    PNode p = NULL;
    PNode pf = NULL;
    p = list;
	pf = p->next;
    while(p)
    {
        if(p->next == NULL)//p是尾节点
        {
            printf("%d",p->data);
            free(p);
            p = pre;//p回移一个节点
            p->next = NULL;
            pre->next = p;
            
        }
        else
        {
        	p = p->next;
            pf = p->next;
			
        }
    }
    return 0;*/
}

/*
4.写一个函数,可以完成一个单链表的就地逆置(不能申请新的节点空间,利用原有的空间)
    Node *reverseList(Node *list)
    改变链表结构	思路：
*/
PNode reverse_linklist(PNode list)
{
	//没有节点或者只有一个节点
	if(list == NULL || list->next == NULL)
		{
		return list;
		}
	Node *p = list;
	Node *q = list->next;
	Node *r = q->next;
	p->next = NULL;//p成为最后一个节点

	while(1)
		{
			q->next = p;
			if(r == NULL)
				{
					return q;
				}
			p=q;
			q=r;
			r=r->next;
			
		}
}

//输出链表
void printf_list(PNode list)
{
    while(list)//直到NULL,结束
	{
		printf("%d ",list->data);
		list=list->next;
	}
	printf("\n");
}

//删除占用空间
void delete_list(PNode l)
{
	//依次释放节点空间
	PNode p = l;
	while(p)
	{
		l = l->next;
		free(p);
		p = l;
	}
}